package com.lab;
import java.io.*;
import java.util.*;

public class Kruskal {
  private final int MAX_NODES = 52;
  @SuppressWarnings("rawtypes")
private HashSet nodes[];               // Array of connected components
  @SuppressWarnings("rawtypes")
private TreeSet allEdges;              // Priority queue of Edge objects
  @SuppressWarnings("rawtypes")
private Vector allNewEdges;            // Edges in Minimal-Spanning Tree

  public static void main(String args[]) {
    System.out.println("Running [Kruskal] - 2000");
   /* if (args.length != 1) {
      System.out.println("Usage: java Kruskal <fileName>");
      System.exit(0);
    }*/
    Kruskal k = new Kruskal();
    k.readInGraphData("C:\\Users\\MUSTANG\\Desktop\\міста3.txt");
    k.performKruskal();
   // k.printFinalEdges();
  }

  Kruskal() {
    // Constructor
    nodes = new HashSet[MAX_NODES];      // Create array for components
    allEdges = new TreeSet(new Edge());  // Create empty priority queue
    allNewEdges = new Vector(MAX_NODES); // Create vector for MST edges
  }

 public void readInGraphData(String fileName) {
    try {
    	System.out.println(fileName);
      FileReader file = new FileReader(fileName);
      BufferedReader buff = new BufferedReader(file);
      String line = buff.readLine();
      while (line != null) {
        StringTokenizer tok = new StringTokenizer(line, ",");
        int from = Integer.valueOf(tok.nextToken()).intValue();
        int to   = Integer.valueOf(tok.nextToken()).intValue();
        int cost = Integer.valueOf(tok.nextToken()).intValue();

        allEdges.add(new Edge(from, to, cost));  // Update priority queue
        if (nodes[from] == null) {
          // Create set of connect components [singleton] for this node
          nodes[from] = new HashSet(2*MAX_NODES);
          nodes[from].add(new Integer(from));
        }

        if (nodes[to] == null) {
          // Create set of connect components [singleton] for this node
          nodes[to] = new HashSet(2*MAX_NODES);
          nodes[to].add(new Integer(to));
        }

        line = buff.readLine();
      }
      buff.close();
    } catch (IOException e) {
      //
    }
  }

  public void performKruskal() {
    int size = allEdges.size();
    for (int i=0; i<size; i++) {
      Edge curEdge = (Edge) allEdges.first();
      if (allEdges.remove(curEdge)) {
        // successful removal from priority queue: allEdges

        if (nodesAreInDifferentSets(curEdge.from, curEdge.to)) {
          // System.out.println("Nodes are in different sets ...");
          HashSet src, dst;
          int dstHashSetIndex;

          if (nodes[curEdge.from].size() > nodes[curEdge.to].size()) {
            // have to transfer all nodes including curEdge.to
            src = nodes[curEdge.to];
            dst = nodes[dstHashSetIndex = curEdge.from];
          } else {
            // have to transfer all nodes including curEdge.from
            src = nodes[curEdge.from];
            dst = nodes[dstHashSetIndex = curEdge.to];
          }

          Object srcArray[] = src.toArray();
          int transferSize = srcArray.length;
          for (int j=0; j<transferSize; j++) {
            // move each node from set: src into set: dst
            // and update appropriate index in array: nodes
            if (src.remove(srcArray[j])) {
              dst.add(srcArray[j]);
              nodes[((Integer) srcArray[j]).intValue()] = nodes[dstHashSetIndex];
            } else {
              // This is a serious problem
              System.out.println("Something wrong: set union");
              System.exit(1);
            }
          }

          allNewEdges.add(curEdge);
          // add new edge to MST edge vector
        } else {
          // System.out.println("Nodes are in the same set ... nothing to do here");
        }

      } else {
        // This is a serious problem
        System.out.println("TreeSet should have contained this element!!");
        System.exit(1);
      }
    }
  }

  private boolean nodesAreInDifferentSets(int a, int b) {
    // returns true if graph nodes (a,b) are in different
    // connected components, ie the set for 'a' is different
    // from that for 'b'
    return(!nodes[a].equals(nodes[b]));
  }

  private void printFinalEdges() {
    System.out.println("The minimal spanning tree generated by "+
      "\nKruskal's algorithm is: ");
    while (!allNewEdges.isEmpty()) {
      // for each edge in Vector of MST edges
      Edge e = (Edge) allNewEdges.firstElement();
      System.out.println("Nodes: (" + e.from + ", " + e.to +
        ") with cost: " + e.cost);
      allNewEdges.remove(e);
    }
  }
  public Vector getNewEdges() {
	    return allNewEdges;
	  }
  }
